#ifndef SET_INT_H
#define SET_INT_H

#include <algorithm>
#include <vector>
#include "assert.h"


template <size_t MAX>
class MaxValueSet
{
public:
    MaxValueSet()
    {
        memset(numbers, 0, sizeof(numbers));
        maxExist = 0;
    }
    MaxValueSet(const std::vector<size_t>& values)
    {
        memset(numbers, 0, sizeof(numbers));
        maxExist = 0;
        for(size_t i = 0; i < values.size(); ++i) {
            add(values[i]);
        }
    }

    void add(size_t v)
    {
        assert(v <= MAX, "v <= MAX");
        numbers[v]++;
        maxExist = std::max(maxExist, v);
    }

    void del(size_t v)
    {
        assert(v <= MAX, "v <= MAX");
        assert(numbers[v] != 0, "numbers[v] != 0");
        numbers[v]--;
        decreaseMaxEsist();
    }

    void change(size_t u, size_t v)
    {
        add(v);
        del(u);
    }

    size_t maxValue() const
    {
        return maxExist;
    }

private:
    void decreaseMaxEsist()
    {
        while (maxExist > 0 && numbers[maxExist] == 0) {
            --maxExist;
        }
    }
    size_t numbers[MAX + 1];
    size_t maxExist;
};

template <size_t MAX>
class MinOutValueSet
{
public:
    MinOutValueSet()
    {
        memset(numbers, 0, sizeof(numbers));
        minOut = 0;
    }
    MinOutValueSet(const std::vector<size_t>& values)
    {
        memset(numbers, 0, sizeof(numbers));
        minOut = 0;
        for(size_t i = 0; i < values.size(); ++i) {
            add(values[i]);
        }
    }

    bool add(size_t v)
    {
        assert(v <= MAX, "v <= MAX");
        size_t before = minOut;
        numbers[v]++;
        increaseMinOut();
        return before != minOut;
    }

    bool del(size_t v)
    {
        assert(v <= MAX, "v <= MAX");
        assert(numbers[v] != 0, "numbers[v] != 0");
        size_t before = minOut;
        numbers[v]--;
        if (v < minOut && numbers[v] == 0) {
            minOut = v;
        }
        return before != minOut;
    }

    bool change(size_t u, size_t v)
    {
        size_t before = minOut;
        del(u);
        add(v);
        return before != minOut;
    }

    size_t minOutside() const
    {
        return minOut;
    }

private:
    void increaseMinOut()
    {
        while (minOut < MAX + 1 && numbers[minOut] > 0) {
            ++minOut;
        }
    }
    size_t numbers[MAX + 2];
    size_t minOut;
};

#endif//SET_INT_H
